//
// Created by LiuYou on 2021/12/5.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>


namespace sort {
    class Sort final {
    public:
        static int random(int left, int right) {
            std::random_device randomDevice;
            std::default_random_engine randomEngine( randomDevice());
            std::uniform_int_distribution<> uniformIntDistribution( left, right );
            return uniformIntDistribution( randomEngine );
        }

    public:
        // 归并排序...
        static void mergeSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            mergeSort( arr, 0, arr.size() - 1 );
        }

        static void mergeSort(std::vector<int>& arr, int left, int right) {
            if (left == right) {
                return;
            } else {
//                int mid = (left + right) / 2;
                int mid = left + ((right - left) >> 1);
                mergeSort( arr, left, mid );
                mergeSort( arr, mid + 1, right );
//                mergeTwoSide( arr, left, mid, right );

                // todo 笔记: 如果使用 STL 提供的 inplace_merge();算法的话, 一定要注意: STL 的区间是 [begin, end)
                //  所以, 这里的实参是 (arr.begin() + left, arr.begin() + mid + 1, arr.begin() + right + 1)。
                //  mid 和 right 都是需要 + 1 的！
                std::inplace_merge( arr.begin() + left,
                                    arr.begin() + mid + 1,
                                    arr.begin() + right + 1 );
            }
        }

        static void mergeTwoSide(std::vector<int>& arr, int left, int mid, int right) {
            std::vector<int> help( right - left + 1 );
            int idx = 0;
            int leftSideIdx = left;
            int rightSideIdx = mid + 1;

            while (leftSideIdx <= mid && rightSideIdx <= right) {
                if (arr[leftSideIdx] <= arr[rightSideIdx]) {
                    help[idx++] = arr[leftSideIdx++];
                } else {
                    help[idx++] = arr[rightSideIdx++];
                }
            }
            while (leftSideIdx <= mid) {
                help[idx++] = arr[leftSideIdx++];
            }
            while (rightSideIdx <= right) {
                help[idx++] = arr[rightSideIdx++];
            }

            for (int i = 0; i < help.size(); ++i) {
                arr[left + i] = help[i];
            }
        }

        // ...归并排序

    public:
        // 快速排序...
        static void quickSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            quickSort( arr, 0, arr.size() - 1 );
        }

        static void quickSort(std::vector<int>& arr, int left, int right) {
            if (left < right) {

                std::swap( arr[random( left, right )], arr[right] );

                const std::vector<int>& pivotRangeIdx = partition( arr, left, right );
                quickSort( arr, left, pivotRangeIdx[0] - 1 );
                quickSort( arr, pivotRangeIdx[1] + 1, right );
            } else {
                return;
            }
        }

        static std::vector<int> partition(std::vector<int>& arr, int left, int right) {
            int pivot = arr[right];
            int idx = left;
            int lessPivotSideIdx = left - 1;
            int greaterPivotSideIdx = right;

            while (idx < greaterPivotSideIdx) {
                if (arr[idx] < pivot) {
                    std::swap( arr[idx++], arr[++lessPivotSideIdx] );
                } else if (arr[idx] == pivot) {
                    ++idx;
                } else {
                    std::swap( arr[idx], arr[--greaterPivotSideIdx] );
                }
            }

            std::swap( arr[idx], arr[right] );
            return std::vector<int>{lessPivotSideIdx + 1, greaterPivotSideIdx};
        }

        // ...快速排序
    };
}


using namespace sort;


int main(int argc, char** argv) {
    std::cout << "===========================[ 归并排序 ]============================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

        Sort::mergeSort( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

    }

    std::cout << "===========================[ 快速排序 ]============================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

        Sort::mergeSort( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

    }

    std::cout << "======================[ STL algorithm: partition(); ]=========================" << std::endl;
    {
        std::vector<int> arr;
        arr.reserve( 10 );
        for (int i = 0; i < 10; ++i) {
            arr.emplace_back( Sort::random( 0, 100 ));
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        std::swap( arr[Sort::random( 0, arr.size() - 1 )], arr[arr.size() - 1] );
        std::cout << "划分值为: " << arr[arr.size() - 1] << std::endl;
        const auto& iter =
                std::stable_partition( arr.begin(), arr.end(), [&](const auto& item) {
//                    if (item < arr[arr.size() - 1]) {
//                        return true;
//                    } else {
//                        return false;
//                    }
                    return item < arr[arr.size() - 1];
                } );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        std::cout << "arr[ " << iter - arr.begin() << " ]" << " = " << *iter << std::endl;
    }


    return 0;
}
